// 给定两个正序数组nums1，nums2，找出并返回这两个正序数组的中位数，算法的时间复杂度应该为O(log(m+n))
// 思路：n1是nums1的数组长度，n2是nums2的数组长度，中位数是第k个数，k = Math.floor((n1 + n2 + 1) / 2), 这里的k不是索引，是第几个
//  从nums1中取出m1个元素，使得nums1的第m1个元素或者nums2的第m2 = k - m1个数视为中位数位置

function findMedianSortedArrays(nums1, nums2) {
    let n1 = nums1.length
    let n2 = nums2.length
    if (n1 > n2) {
        return findMedianSortedArrays(nums2, nums1)
    }
    let k = Math.floor((n1 + n2 + 1) / 2)
    let left = 0
    let right = n1
    while (left < right) {
        // 在nums1中取前m1个元素
        let m1 = left + Math.floor((right - left) / 2)
        // 在nums2中取前m2个元素
        let m2 = k - m1
        // 此时，nums2[m2-1] 这个元素比 nums1[m1] 大，但它却被划分到了左半部分，导致左半部分的最大值可能超过右半部分的最小值
        if (nums1[m1] < nums2[m2 - 1]) {
            // 说明 nums1中元素不够多
            left = m1 + 1
        } else {
            right = m1
        }
    }
    let m1 = left
    let m2 = k - m1
    let c1 = Math.max(m1 <= 0 ? -Infinity : nums1[m1 - 1], m2 <= 0 ? -Infinity : nums2[m2 - 1])
    if ((n1 + n2) % 2 === 1) {
        return c1
    }
    let c2 = Math.min(m1 >= n1 ? Infinity : nums1[m1], m2 >= n2 ? Infinity : nums2[m2])
    return (c1 + c2) / 2
}

let arr1 = [1, 2, 3, 4]
let arr2 = [3, 4, 5, 6, 7]
console.log(findMedianSortedArrays(arr1, arr2));